#include "DS/KBIT.h"
#include "IO/FastIO.h"
#include "MATH/StaticModInt32.h"

void test() {
    using mint = OY::mint1000000007;
    using KBIT = OY::KBIT::Tree<mint, 5>;
    KBIT::prepare();

    int a[9] = {4, 9, 2, 3, 5, 7, 8, 1, 6};
    KBIT S(a, a + 9);

    // 把原数组和各阶前缀和输出
    auto print = [&]() {
        cout << "orignal array:\t";
        for (int idx = 0; idx < 9; idx++) cout << S.query<1>(idx) - S.query<1>(idx - 1) << " \n"[idx == 8];
        for (int idx = 0; idx < 9; idx++) cout << S.query<1>(idx) << " \n"[idx == 8];
        for (int idx = 0; idx < 9; idx++) cout << S.query<2>(idx) << " \n"[idx == 8];
        for (int idx = 0; idx < 9; idx++) cout << S.query<3>(idx) << " \n"[idx == 8];
        for (int idx = 0; idx < 9; idx++) cout << S.query<4>(idx) << " \n"[idx == 8];
        for (int idx = 0; idx < 9; idx++) cout << S.query<5>(idx) << " \n"[idx == 8];
        cout << endl;
    };
    print();

    // 给 5 阶前缀和表下标 0~3 添加 (100000,400000,900000,1600000)
    // 也就是多项式 (i+1)^2 * 100000
    S.add<5>(0, 3, std::array<mint, 3>{100000, 200000, 100000});
    print();

    // 给 2 阶前缀和表下标 1~4 添加 (1,2,3,4)
    // 也就是多项式 i^1
    S.add<2>(1, 4, std::array<mint, 2>{0, 1});
    print();
}

int main() {
    test();
}
/*
#输出如下
orignal array:	4 9 2 3 5 7 8 1 6
4 13 15 18 23 30 38 39 45
4 17 32 50 73 103 141 180 225
4 21 53 103 176 279 420 600 825
4 25 78 181 357 636 1056 1656 2481
4 29 107 288 645 1281 2337 3993 6474

orignal array:	100004 999900016 999900009 100003 997500012 8900007 988100015 7100001 998400013
100004 13 999900022 18 997500030 6400030 994500045 1600039 45
100004 100017 32 50 997500080 3900103 998400148 180 225
100004 200021 200053 200103 997700183 1600279 420 600 825
100004 300025 500078 700181 998400364 636 1056 1656 2481
100004 400029 900107 1600288 645 1281 2337 3993 6474

orignal array:	100004 999900017 999900009 100003 997500012 8900002 988100019 7100001 998400013
100004 14 999900023 19 997500031 6400026 994500045 1600039 45
100004 100018 34 53 997500084 3900103 998400148 180 225
100004 200022 200056 200109 997700193 1600289 430 610 835
100004 300026 500082 700191 998400384 666 1096 1706 2541
100004 400030 900112 1600303 680 1346 2442 4148 6689

*/